package com.wuyong.chapter5;

/**
 *删除链表中等于给定值 val 的所有节点。

 示例:

 输入: 1->2->6->3->4->5->6, val = 6
 输出: 1->2->3->4->5
 */
public class Solution {

    public ListNode removeElements(ListNode head, int val) {

        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = delNode.next;
            delNode.next = null;
        }
        if (head == null) {
            return head;
        }

        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            } else {
                prev = prev.next;
            }
        }
        return head;

    }
    //改进
    public ListNode removeElements2(ListNode head, int val) {

        while (head != null && head.val == val) {

            head = head.next;
        }
        if (head == null) {
            return head;
        }
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return head;
    }
    //使用虚拟头结点
    public ListNode removeElements3(ListNode head, int val) {

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return dummyNode.next;
    }

    //使用递归解决
    public ListNode removeElements4(ListNode head, int val) {

        if (head == null) {
            return new ListNode(-1);
        }
        ListNode res = removeElements4(head.next, val);
        if (head.val == val) {
            return res;
        } else {
            head.next = res;
            return head;
        }
    }

    //使用递归解决
    public ListNode removeElements5(ListNode head, int val) {

        if (head == null) {
            return null;
        }
        head.next = removeElements5(head.next, val);
        return head.val == val ? head.next : head;
    }


    public static void main(String[] args) {
        int[] nums = {3, 5, 6, 8, 6};
        ListNode listNode = new ListNode(nums);
        System.out.println(listNode);
        new Solution().removeElements4(listNode, 6);
        System.out.println(listNode);
    }
}
